package problem.ej2;


import java.util.Collections;
import java.util.LinkedList;
import java.util.PriorityQueue;
import java.util.TreeSet;
import java.util.Vector;
import java.util.Comparator;
import java.util.Iterator;

/*
 * @Grafo: es como representaremos al "grafo" derivado de las conecciones entre localidades.
 * A cada eje lo guardaremos en la lista de ambos vértices que tiene como extremos
 * Al Grafo lo representaremos como un vector de vértices que contiene una lista de tupla <inicio, destino,costo>.
 * Obviamente, como no es un digrafo, el destino es una "sobre-notación" ya que no hay destino ni origen (ambos 
 * "salen y llegan").
 * Cosas a tener en cuenta:
 * 1) Hay una biyección entre el nombre del vértice que nos llega y el nombre del vértice del grafo. Es decir, 
 * puede que en la entrada una localidad tenga el número "3" y en nuestro grafo sea representado por el vértice
 * "10", pero podemos trancisionar entre el "10" y el "3" y viceversa sin ambigüedad.
 * (Lo de arriba se debe a que no sabemos con seguridad cómo nos van a llegar los vértices y por eso nos "aseguramos
 * la bocha" )
 */
public class Grafo {
	
	/*
	 * @vertices: es el vector de vértices con el que representaremos a los vértices propiamentedichos y a los 
	 * ejes que unen a estos entre sí.
	 */
	private Vector<LinkedList<tupla_eje> > vertices;
	/*
	 * @de_pos_a_localidad_original:
	 * Sería como una función biyectiva que transforma el "nombre" de la localidad provienente del archivo
	 * al "nombre" que le damos nosotros para poder usar la matriz de adyacencia sin problemas.
	 * La posición en el arreglo representa el número que le damos nosotros para usarlo en el vector
	 * "vértices" y el contenido de esa posición representa el valor original que vino del archivo.
	 */
	private int[] de_pos_a_localidad_original;
	int cant_ejes;

	/*
	 * @Constructor:
	 * es el constructor de la clase y recibe como parámetro una lista de arreglos en la que cada uno representa
	 * a una arista y son de longitud 3: la primera posición es un vértice, la 2da posición otro vértice y la
	 *  3ra el peso de la arista.
	 */
	public Grafo(LinkedList<tupla_eje> lista_adyacencia){
/*-----------DESDE ACÁ PASAMOS LA LISTA A UN VECTOR, LO ORDENAMOS PARA TENER LOS EJES REPETIDOS SEGUIDOS E INICIALIZAMOS
-------------EL ARREGLO "de_pos_a_localidad_original" USANDO UN SET PARA SACAR LOS VÉRTICES REPETIDOS	
 */
		/*Primero paso la lista a vector*/
		Vector<tupla_eje> vector_adyacencia = new Vector<tupla_eje>(lista_adyacencia);
		/*como es grafo y no digrafo, no me importa el orden entre de las localidades de un mismo eje,
		 * entonces las reordeno entre sí si la loc1 es mayor a la loc2*/
		for(int i = 0; i < vector_adyacencia.size(); i++){
			if(vector_adyacencia.elementAt(i).inicio > vector_adyacencia.elementAt(i).destino){
				int temp = vector_adyacencia.elementAt(i).inicio;
				vector_adyacencia.elementAt(i).inicio = vector_adyacencia.elementAt(i).destino;
				vector_adyacencia.elementAt(i).destino = temp;
			}
			/*Osea, si la loc1 es menor a la loc2, que las intercambie*/
		}
		/*Después ordeno el vector teniendo en cuenta primero la primer localidad y después la 2da */
		Comparator<tupla_eje> byloc1thenloc2 = new comp_loc1_vs_loc2_eje();
		
		Collections.sort(vector_adyacencia, byloc1thenloc2);
		/*Hasta acá es todo O(long(lista_adyacencia)*log(long(lista_adyacencias))*/
		/*Ahora veo cuántas localidades distintas hay y le asigno a cada una un identificador en el grafo*/
		/* |CUIDADO: localidad != eje| */
		TreeSet<Integer> set_vertices = new TreeSet<Integer>();
		for(int i = 0; i < vector_adyacencia.size(); i++){
			set_vertices.add(vector_adyacencia.elementAt(i).destino);
			set_vertices.add(vector_adyacencia.elementAt(i).inicio);
			/*Agrego ambas localidades. Si ya estaban no importa, de eso se arregla el Set internamente
			 * para no admitir elementos repetidos.*/
		}
		/*Ya tengo el set con los vértices sin repetir*/
		de_pos_a_localidad_original = new int[set_vertices.size()]; /*lo genero con cantidad de vértices sin repetir*/
		vertices= new Vector<LinkedList<tupla_eje> >(set_vertices.size()); /* me reserva la capacity para el vector*/
		/*ahora lleno el vector con listas vacías para no tener problemas más adelante*/
		for(int i = 0; i<vertices.capacity(); i++) vertices.add(new LinkedList<tupla_eje>());
		
		/*Ahora le asigno a cada vértice de mi grafo su respectiva localidad*/
		Iterator<Integer> it_set = set_vertices.iterator();
		for(int i = 0; i < de_pos_a_localidad_original.length; i++){
			de_pos_a_localidad_original[i] = it_set.next();
		}
		
///-----------------HASTA ACÁ TENEMOS TODO TERMINADO MENOS AL VECTOR VÉRTICES (aunque ya está llenado con listas vacías). 
///-----------------LO LLENAREMOS CON EJES PERO SI HAY 2 EJES CON LOS MISMOS EXTREMOS, ENTONCES SÓLO TENDREMOS EN CUENTA
///-----------------EL EJE CON MENOR COSTO ENTRE TODOS LOS EJES CON MISMAS INCIDENCIAS.

		/*Primero lleno la primer posición (siempre hay por lo menos un eje.)
		 * (lo hago para después no tener problemas adentro del for)*/
		int ultima_loc1= vector_adyacencia.elementAt(0).inicio;
		int ultima_loc2= vector_adyacencia.elementAt(0).destino;
		int ultimo_peso = vector_adyacencia.elementAt(0).costo;
		/*a estos ints los uso principalmente como optimización. Nada más (así no tiene que ejecutar todo lo del
		 *  for de abajo cuando hay muchos ejes repetidos seguidos)*/
		cant_ejes = 0;/*Cada vez que agregue un eje, le sumo uno a cant_ejes*/
		for(int i = 1; i < vector_adyacencia.size(); i++){
			/*mientras no haya visto todos los elementos de la lista, que siga*/
			/*ya sé que el vector está ordenado y siempre loc1 <= loc2*/
			/*Sólo modificaré el vector "vértices" cuando termine de iterar todos los ejes iguales consecutivos
			 * y por ende ya tenga el peso mínimo de todos estos*/
			int loc1 = vector_adyacencia.elementAt(i).inicio;
			int loc2 = vector_adyacencia.elementAt(i).destino;
			int peso = vector_adyacencia.elementAt(i).costo;
			
			if((ultima_loc1 != loc1) || (ultima_loc2 != loc2)){
				/*si se cumple la guarda entonces el eje cambió: pasé a un nuevo eje entonces ahora agrego
				 *  el eje viejo al "vértices" (cambió alguno de los 2 vértices incididos 
				 *  de la tupla comparado con el eje (la tupla) anterior)*/
				tupla_eje tupla = new tupla_eje();
				int pos_vertices_desde = deLocAVertice(ultima_loc1);
				int pos_vertices_hasta = deLocAVertice(ultima_loc2);
				
				tupla.costo = ultimo_peso;
				tupla.destino = pos_vertices_hasta;
				tupla.inicio = pos_vertices_desde; /*Lo agrego porque en el Heap lo voy a necesitar*/
				vertices.elementAt(pos_vertices_desde).add(tupla);
				vertices.elementAt(pos_vertices_hasta).add(tupla);
				cant_ejes++;
				
				ultima_loc1 = loc1;
				ultima_loc2 = loc2;
				ultimo_peso = peso;
			}
			else{
				/*es el "mismo eje": entonces veo si actualizo el peso mínimo temporal*/
				if(ultimo_peso > peso) ultimo_peso = peso;
				if(i==vector_adyacencia.size()-1){
					/*Si es la última posición y venía en "tanda" de ejes iguales, si no agrego este if no agrega el mínimo
					 * de la tanda propiamente dicha.
					 * En otras palabras: siempre voy a tener que agregar el eje de la última posición, no importa
					 * cuál sea éste.*/
					
					tupla_eje tupla = new tupla_eje();
					int pos_vertices_desde = deLocAVertice(ultima_loc1);
					int pos_vertices_hasta = deLocAVertice(ultima_loc2);
					
					tupla.costo = ultimo_peso;
					tupla.destino = pos_vertices_hasta;
					tupla.inicio = pos_vertices_desde; /*Lo agrego porque en el Heap lo voy a necesitar*/
					vertices.elementAt(pos_vertices_desde).add(tupla);
					vertices.elementAt(pos_vertices_hasta).add(tupla);
					cant_ejes++;
				}
			}
/*-----------------acá termina el generador del grafo.--------------------------------------------*/	
		}
			
	}
	/*
	 * @arbol_gen: es la función que busca el árbol generador mínimo de la instancia.
	 * Cosas a tener en cuenta:
	 * 1) Devuelve los ejes con los vértices nombrados como en la entrada. Recordar que cuando leemos un eje, a cada vértice
	 * le asignamos un ID en nuestro grafo, ya que no nos aseguran que vengan en secuencia. El grafo contiene a los vértices
	 * con los nombres cambiados y éstos nuevos nombres en secuencia. Árbol_gen antes de terminar hace la trancisión entre
	 * los nombres nuestros y los nombres con los que vino la instancia.
	 */
	LinkedList<tupla_eje> arbol_gen(){
		LinkedList<tupla_eje> res = new LinkedList<tupla_eje>();
		
		/*itero el verctor vertices y voy guardando qué vértices ya están en el árbol*/
		
		
		boolean[] array_estan = new boolean[vertices.size()];
		for(int i = 0; i < array_estan.length; i++){
			array_estan[i] = false;
		}
		/*Array_estan es el array que voy a usar para ver si un vértice ya pertenece a mi resultado parcial*/
		Comparator<tupla_eje> byPeso = new comp_peso_tupla_eje();
		PriorityQueue<tupla_eje> cola = new PriorityQueue<tupla_eje>(cant_ejes, byPeso);/*byPeso es el comparator
		que usa para mantener el invariante de que la cola esté siempre ordenada*/
		
		/*Tengo que agregar los ejes del primer vértice a mano sí o sí
		 * (para después no tener problemas adentro del while)*/
		array_estan[0] = true;
		Iterator<tupla_eje> iter_tupla = vertices.elementAt(0).iterator();
		tupla_eje tupla;
		while(iter_tupla.hasNext()){
			tupla = iter_tupla.next();
			if((array_estan[tupla.destino] &&  (!array_estan[tupla.inicio])) || 
					((!array_estan[tupla.destino]) &&  array_estan[tupla.inicio])){
				/*Si uno está pero el otro no, que agregue la tupla a la cola (es lo que mira la guarda).
				 * En el caso en el que ambos estén, no hace nada. 
				 * No puede ser que no esté ninguno por cómo venía iterando los vértices (por lo menos uno siempre está).*/
				cola.add(tupla);
			}
		}
		int cant_vertices_afuera = vertices.size() -1; /*menos 1 porque ya agregué el primero*/
		
		while(cant_vertices_afuera > 0){
			/*Como asumo que es conexo el grafo, la cola nunca va a estar vacía antes de que termine
			 * de agregar a los vértices porque siempre le voy a estar agregando ejes mientras
			 * agregue vértices*/
			
			tupla = cola.poll();
			while((array_estan[tupla.destino] &&  array_estan[tupla.inicio])){
				/*Si están ambos vértices ya en mi árbol temporario, que discarde el eje y busque otro
				 * Nunca voy a "discardear" un eje 2 veces ya que siempre lo agrego sólo una vez ya que sólo hay
				 * 2 formas que lo mire:
				 * 1) Cuando esté iterando el vértice "padre": la primera vez que lo agrego
				 * 2) Cuando esté iterando el vértice "hijo": la 2da vez que paso por ahí. Como
				 * ya ambos nodos están en mi árbol gen temp entonces no agrego al eje (sigo de largo).
				 * (ser tolerante con "padre" e "hijo") */
				tupla = cola.poll();
			}
			/*Entonces, ahora en tupla tengo un eje con peso mínimo y un extremo adentro y el otro extremo afuera.
			 * Es el eje elegido: agrego el de afuera a mi árbol y sus ejes a la cola*/
			res.add(tupla);
/*-------------|CUIDADO|: res NO contiene los vértices nombrados como en la entrada. Contiene los ejes nombrados como en mi grafo*/
/*-------------Al terminar con la lista, pasamos los nombres de los vértices a los nombres reales.*/
/*------------- Es decir, a los nombres con los que vinieron los vértices*/
	
			int vert_actual;
			if (array_estan[tupla.destino]) vert_actual = tupla.inicio;
			else vert_actual = tupla.destino;
			/*El if de arriba: vert_actual es el vértice que está afuera (el otro ya está adentro)*/
			array_estan[vert_actual] = true;
			cant_vertices_afuera--;
			
			iter_tupla = vertices.elementAt(vert_actual).iterator();/*Itero los ejes del vert_actual*/
			while(iter_tupla.hasNext()){
				tupla = iter_tupla.next();
				if((array_estan[tupla.destino] &&  (!array_estan[tupla.inicio])) || 
						((!array_estan[tupla.destino]) &&  array_estan[tupla.inicio])){
					/*Si uno está pero el otro no, que lo agregue. Si ambos están, no lo considera. No puede pasar
					 * que no esté ninguno por cómo venía iterando los vértices (por lo menos uno siempre está).*/
					cola.add(tupla);
				assert(array_estan[tupla.destino] || array_estan[tupla.inicio]);
				}				
			}
		}
		
		return de_Nombre_grafo_a_nombre_Real(res);
	}
	LinkedList<tupla_eje> de_Nombre_grafo_a_nombre_Real(LinkedList<tupla_eje> list){
		Iterator<tupla_eje> iter_tupla = list.iterator();
		
		while(iter_tupla.hasNext()){
			tupla_eje tupla = iter_tupla.next();
			int loc1_real = deVerticeALoc(tupla.inicio);
			int loc2_real = deVerticeALoc(tupla.destino);
			tupla.inicio = loc1_real;
			tupla.destino = loc2_real;
			}
		return list;
	}
		
	int deVerticeALoc (int vert){
		return de_pos_a_localidad_original[vert];
	}
	
	int deLocAVertice(int loc){
		/*Complejidad en peor caso: O(cantidad vértices) == O(Cantidad localidades)*/
		int i;
		for(i = 0; i< de_pos_a_localidad_original.length; i++){
			if(de_pos_a_localidad_original[i] == loc) break;
		}
			return i;
	}
	
	class comp_loc1_vs_loc2_eje implements Comparator<tupla_eje> {
	
		public int compare(tupla_eje a, tupla_eje b) {
			if(a.inicio < b.inicio) return -1;
			if((a.inicio <= b.inicio) && (a.destino < b.destino)) return -1;
			if((a.inicio <= b.inicio) && (a.destino == b.destino)) return 0;
			else return 1;
	    }
	}
	
	class comp_peso_tupla_eje implements Comparator<tupla_eje> {
		
		public int compare(tupla_eje a, tupla_eje b) {

			if(a.costo < b.costo) return -1;
			if(a.costo > b.costo) return 1;
			else return 0;
	    }
	}
	
	public static void main(String[] args){
//		1 2 1;1 2 4;2 3 2;2 3 3;2 3 1;3 4 2;1 4 3;2 4 2;2 4 5
		LinkedList<tupla_eje> inst_1 = new LinkedList<tupla_eje>();
		tupla_eje tupla = new tupla_eje();
//		1 2 1;
		tupla.inicio=1; tupla.destino=2; tupla.costo=1;
		inst_1.add(tupla);
//		1 2 4;		
		tupla = new tupla_eje(); tupla.inicio=1; tupla.destino=2; tupla.costo=4;
		inst_1.add(tupla);
//		2 3 2;		
		tupla = new tupla_eje(); tupla.inicio=2; tupla.destino=3; tupla.costo=2;
		inst_1.add(tupla);
//		2 3 3;2 3 1;3 4 2;1 4 3;2 4 2;2 4 5
		tupla = new tupla_eje(); tupla.inicio=2; tupla.destino=3; tupla.costo=3;
		inst_1.add(tupla);
//		2 3 1;3 4 2;1 4 3;2 4 2;2 4 5		
		tupla = new tupla_eje(); tupla.inicio=2; tupla.destino=3; tupla.costo=1;
		inst_1.add(tupla);
//		3 4 2;1 4 3;2 4 2;2 4 5		
		tupla = new tupla_eje(); tupla.inicio=3; tupla.destino=4; tupla.costo=2;
		inst_1.add(tupla);
//		1 4 3;2 4 2;2 4 5		
		tupla = new tupla_eje(); tupla.inicio=1; tupla.destino=4; tupla.costo=3;
		inst_1.add(tupla);
//		2 4 2;2 4 5
		tupla = new tupla_eje(); tupla.inicio=2; tupla.destino=4; tupla.costo=2;
		inst_1.add(tupla);
//		2 4 5		
		tupla = new tupla_eje(); tupla.inicio=2; tupla.destino=4; tupla.costo=5;
		inst_1.add(tupla);
		Grafo g = new Grafo(inst_1);
		LinkedList<tupla_eje> res_inst_1 = g.arbol_gen();
/*--------------------------------------------------------------------------------------------*/		
//		1 2 4;1 2 2;2 3 1;2 3 2;1 4 2;2 4 3;3 4 1;3 4 3
		LinkedList<tupla_eje> inst_2 = new LinkedList<tupla_eje>();
		tupla = new tupla_eje();
//		1 2 4;1 2 2;2 3 1;2 3 2;1 4 2;2 4 3;3 4 1;3 4 3
		tupla.inicio=1; tupla.destino=2; tupla.costo=4;
		inst_2.add(tupla);
//		1 2 2;2 3 1;2 3 2;1 4 2;2 4 3;3 4 1;3 4 3
		tupla = new tupla_eje(); tupla.inicio=1; tupla.destino=2; tupla.costo=2;
		inst_2.add(tupla);
//		2 3 1;2 3 2;1 4 2;2 4 3;3 4 1;3 4 3
		tupla = new tupla_eje(); tupla.inicio=2; tupla.destino=3; tupla.costo=1;
		inst_2.add(tupla);
//		2 3 2;1 4 2;2 4 3;3 4 1;3 4 3
		tupla = new tupla_eje(); tupla.inicio=2; tupla.destino=3; tupla.costo=2;
		inst_2.add(tupla);
//		1 4 2;2 4 3;3 4 1;3 4 3	
		tupla = new tupla_eje(); tupla.inicio=1; tupla.destino=4; tupla.costo=2;
		inst_2.add(tupla);
//		2 4 3;3 4 1;3 4 3		
		tupla = new tupla_eje(); tupla.inicio=2; tupla.destino=4; tupla.costo=3;
		inst_2.add(tupla);
//		3 4 1;3 4 3	
		tupla = new tupla_eje(); tupla.inicio=3; tupla.destino=4; tupla.costo=1;
		inst_2.add(tupla);
//		3 4 3
		tupla = new tupla_eje(); tupla.inicio=3; tupla.destino=4; tupla.costo=3;
		inst_2.add(tupla);
		Grafo g2 = new Grafo(inst_2);
		LinkedList<tupla_eje> res_inst_2 = g2.arbol_gen();
/*---------------------------------------------------------------------------------------------*/
//		1 2 2;1 2 4;2 3 2;2 3 3;2 3 8;3 1 1;3 1 3;3 1 5;1 4 2;1 4 9
		LinkedList<tupla_eje> inst_3 = new LinkedList<tupla_eje>();
		tupla = new tupla_eje();
//		1 2 2;1 2 4;2 3 2;2 3 3;2 3 8;3 1 1;3 1 3;3 1 5;1 4 2;1 4 9
		tupla.inicio=1; tupla.destino=2; tupla.costo=2;
		inst_3.add(tupla);
//		1 2 4;2 3 2;2 3 3;2 3 8;3 1 1;3 1 3;3 1 5;1 4 2;1 4 9
		tupla = new tupla_eje(); tupla.inicio=1; tupla.destino=2; tupla.costo=4;
		inst_3.add(tupla);
//		2 3 2;2 3 3;2 3 8;3 1 1;3 1 3;3 1 5;1 4 2;1 4 9
		tupla = new tupla_eje(); tupla.inicio=2; tupla.destino=3; tupla.costo=2;
		inst_3.add(tupla);
//		2 3 3;2 3 8;3 1 1;3 1 3;3 1 5;1 4 2;1 4 9
		tupla = new tupla_eje(); tupla.inicio=2; tupla.destino=3; tupla.costo=3;
		inst_3.add(tupla);
//		2 3 8;3 1 1;3 1 3;3 1 5;1 4 2;1 4 9	
		tupla = new tupla_eje(); tupla.inicio=2; tupla.destino=3; tupla.costo=8;
		inst_3.add(tupla);
//		3 1 1;3 1 3;3 1 5;1 4 2;1 4 9			
		tupla = new tupla_eje(); tupla.inicio=3; tupla.destino=1; tupla.costo=1;
		inst_3.add(tupla);
//		3 1 3;3 1 5;1 4 2;1 4 9				
		tupla = new tupla_eje(); tupla.inicio=3; tupla.destino=1; tupla.costo=3;
		inst_3.add(tupla);
//		3 1 5;1 4 2;1 4 9				
		tupla = new tupla_eje(); tupla.inicio=3; tupla.destino=1; tupla.costo=5;
		inst_3.add(tupla);
//		1 4 2;1 4 9				
		tupla = new tupla_eje(); tupla.inicio=1; tupla.destino=4; tupla.costo=2;
		inst_3.add(tupla);
//		1 4 9				
		tupla = new tupla_eje(); tupla.inicio=1; tupla.destino=4; tupla.costo=9;
		inst_3.add(tupla);
		Grafo g3 = new Grafo(inst_3);
		LinkedList<tupla_eje> res_inst_3 = g3.arbol_gen();
/*---------------------------------------------------------------------------------------------*/
//		1 2 2;1 2 5;1 2 9;2 3 4;2 3 5;2 3 6;3 1 7;3 1 8;3 1 10
		LinkedList<tupla_eje> inst_4 = new LinkedList<tupla_eje>();
		tupla = new tupla_eje();
//		1 2 2;1 2 5;1 2 9;2 3 4;2 3 5;2 3 6;3 1 7;3 1 8;3 1 10
		tupla.inicio=1; tupla.destino=2; tupla.costo=2;
		inst_4.add(tupla);
//		1 2 5;1 2 9;2 3 4;2 3 5;2 3 6;3 1 7;3 1 8;3 1 10
		tupla = new tupla_eje(); tupla.inicio=1; tupla.destino=2; tupla.costo=5;
		inst_4.add(tupla);
//		1 2 9;2 3 4;2 3 5;2 3 6;3 1 7;3 1 8;3 1 10
		tupla = new tupla_eje(); tupla.inicio=1; tupla.destino=2; tupla.costo=9;
		inst_4.add(tupla);
//		2 3 4;2 3 5;2 3 6;3 1 7;3 1 8;3 1 10
		tupla = new tupla_eje(); tupla.inicio=2; tupla.destino=3; tupla.costo=4;
		inst_4.add(tupla);
//		2 3 5;2 3 6;3 1 7;3 1 8;3 1 10	
		tupla = new tupla_eje(); tupla.inicio=2; tupla.destino=3; tupla.costo=5;
		inst_4.add(tupla);
//		2 3 6;3 1 7;3 1 8;3 1 10				
		tupla = new tupla_eje(); tupla.inicio=2; tupla.destino=3; tupla.costo=6;
		inst_4.add(tupla);
//		3 1 7;3 1 8;3 1 10								
		tupla = new tupla_eje(); tupla.inicio=3; tupla.destino=1; tupla.costo=7;
		inst_4.add(tupla);
//		3 1 8;3 1 10												
		tupla = new tupla_eje(); tupla.inicio=3; tupla.destino=1; tupla.costo=8;
		inst_4.add(tupla);
//		3 1 10																
		tupla = new tupla_eje(); tupla.inicio=3; tupla.destino=1; tupla.costo=10;
		inst_4.add(tupla);
		Grafo g4 = new Grafo(inst_4);
		LinkedList<tupla_eje> res_inst_4 = g4.arbol_gen();
		int pepe = res_inst_4.size();
	}

}
